package Leetcode.ArrayAndLinkedList.reverseKGroup25;

/**
 * 次数2
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k < 2) {
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        ListNode end = dummyHead;
        dummyHead.next = head;
        ListNode prev = dummyHead;
        while (end.next != null ) {
            for (int i = 0; i < k ; i++) {
                end = end.next;
            }
            if(end == null) {
                break;
            }

            ListNode tmp = end.next;
            end.next = null;
            ListNode start = prev.next;
            prev.next = reverse(start);
            prev = start;
            end = start;
            end.next = tmp;
        }


        return dummyHead.next;
    }

    public ListNode reverse(ListNode start) {
        ListNode cur = start;
        ListNode prev = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }


    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 7,1};
        ListNode node = new ListNode(nums);
        System.out.println(node);

        Solution solution = new Solution();
        System.out.println(solution.reverseKGroup(node, 2));
    }
}


/**
 * public ListNode reverseKGroup(ListNode head, int k) {
 * if (head == null || head.next == null) {
 * return head;
 * }
 * //如果无节点或节点只有一个 则返回
 * ListNode dummyHead = new ListNode(0);
 * dummyHead.next = head;
 * ListNode prev = dummyHead;
 * ListNode end = dummyHead;
 * //将链表分成三部分 已经倒置的部分 待倒置部分 未倒置部分
 * <p>
 * while (end.next != null) {
 * <p>
 * for (int i = 0; i < k && end != null; i++) {
 * end = end.next;
 * }
 * <p>
 * if (end == null) {
 * break;
 * }
 * <p>
 * ListNode next = end.next;
 * ListNode start = prev.next;
 * end.next = null;
 * prev.next = reverse(start);
 * start.next = next;
 * prev = start;
 * end = start;
 * <p>
 * <p>
 * }
 * return dummyHead.next;
 * }
 * <p>
 * /**
 * 1 -> 2 -> 3 反转成3 -> 2 -> 1 并返回头节点3
 *
 * @param head
 * @return public ListNode reverse(ListNode head) {
 * ListNode cur = head;
 * ListNode prev = null;
 * while (cur != null) {
 * ListNode next = cur.next;
 * cur.next = prev;
 * prev = cur;
 * cur = next;
 * }
 * return prev;
 * }
 */
/**
 public ListNode reverse(ListNode head) {
 ListNode cur = head;
 ListNode prev = null;
 while (cur != null) {
 ListNode next = cur.next;
 cur.next = prev;
 prev = cur;
 cur = next;
 }
 return prev;
 }
 */
